#pragma once

#include <vector>
#include "typelib/types.h"

namespace img { class bitmap; }

namespace outline {

typedef point<unsigned short> point_us;
typedef point<short>	point_s;
typedef point<int>		point_i;
typedef point<float>	point_f;
typedef point<double>	point_d;

typedef std::vector<point_us>	outline_us;
typedef std::vector<point_s>	outline_s;
typedef std::vector<point_i>	outline_i;
typedef std::vector<point_f>	outline_f;
typedef std::vector<point_d>	outline_d;

template <typename T>
inline bool closed(std::vector<T> const & o) 
	{ return o[0] == o[o.size()-1]; }

/// returns true if closed outline is oriented in counter-clockwise order (y axis is pointing down)
template <typename T>
bool ccw_orientation(std::vector<T> const & o);

//multiple outlines
typedef std::vector<outline_us> outlines_us;
typedef std::vector<outline_s> outlines_s;
typedef std::vector<outline_i> outlines_i;
typedef std::vector<outline_f> outlines_f;
typedef std::vector<outline_d> outlines_d;

///finds all closed and open contours on the bitmap and pushes them to outlines list
///each outline is oriented so that set bits lie on the left, and reset on the right (y axis is pointing down)
void trace(img::bitmap const & b, outlines_us & os, bool close_all = false);

///shifts start point of closed contour on s node
///\param it is acceptable for src and dst to coincide
template <typename T>
void shift(std::vector<T> const & src, std::vector<T> & dst, int s);

template <typename T>
double length(std::vector< point<T> > const & polyline);

// if normalize than each partial length will be divided on total length and
// partial_lengths.front() == 0, ..., partial_lengths.back() == 1
// if not normalize then
// partial_lengths.front() == 0, ..., partial_lengths.back() == total_length
// in either case total length is returned
template <typename T, typename R>
R length(std::vector< point<T> > const & polyline, std::vector<R> & partial_lengths, bool normalize);

// Implementation

template <typename T>
void shift(std::vector<T> const & src, std::vector<T> & dst, int s)
{
	if (s == 0 && &src == &dst)
		return;
	size_t const m = src.size();
	assert(src[0] == src[m-1]);
	std::vector<T> tmp(m);
	std::copy(src.begin() + s, src.end(), tmp.begin()); //copy of m-s elements 
	std::copy(src.begin() + 1, src.begin() + s+1, tmp.begin() + m-s); //copy of s elements 
	dst.swap(tmp);
	assert(dst[0] == dst[m-1]);
}

template <typename T>
bool ccw_orientation(std::vector<T> const & o)
{
	assert (closed(o));
	size_t size = o.size();
	double area = 0; //double is not good for general case :(
	point<double> o0(o[0]);
	for (size_t i = 1; i+1 < size; ++i)
		area += outer_product(point<double>(o[i]) - o0, point<double>(o[i+1]) - o0);
	return area < 0;
}

} //namespace outline
